/// @tags: SAM SegmentTree
#include <cstdio>
#include <cstring>
#include <iostream>

using namespace std;

namespace BlueQuantum {

typedef long long LL;

constexpr int MAXN = 2e5 + 3, INF = 0x3f3f3f3f, ST = 19, CHARSET = 10;

struct Node {
  int min, max;
  LL sum1, sum2;
} tr[MAXN * 35];

struct Segment_Tree {
  int ch[MAXN * 35][2], tot;

  inline Node merge(const Node &a, const Node &b) {
    Node c;
    c.min = min(a.min, b.min);
    c.max = max(a.max, b.max);
    c.sum1 = a.sum1 + b.sum1 + b.min * 1LL * (b.min - a.max);
    c.sum2 = a.sum2 + b.sum2 + b.min - a.max;
    return c;
  }

  int queryMax(int l, int r, int rt, int L, int R) {
    if (!rt) return 0;
    if (L <= l && r <= R) return tr[rt].max;
    int mid = (l + r) >> 1, ans = 0;
    if (L <= mid) ans = queryMax(l, mid, ch[rt][0], L, R);
    if (R > mid) ans = max(ans, queryMax(mid + 1, r, ch[rt][1], L, R));
    return ans;
  }

  int queryMin(int l, int r, int rt, int L, int R) {
    if (!rt) return INF;
    if (L <= l && r <= R) return tr[rt].min;
    int mid = (l + r) >> 1, ans = INF;
    if (L <= mid) ans = queryMin(l, mid, ch[rt][0], L, R);
    if (R > mid) ans = min(ans, queryMin(mid + 1, r, ch[rt][1], L, R));
    return ans;
  }

  Node tmp;
  void query(int l, int r, int rt, int L, int R) {
    if (!rt) return;
    if (L <= l && r <= R) {
      if (tmp.min == 0)
        tmp = tr[rt];
      else
        tmp = merge(tmp, tr[rt]);
      return;
    }
    int mid = (l + r) >> 1;
    if (L <= mid) query(l, mid, ch[rt][0], L, R);
    if (R > mid) query(mid + 1, r, ch[rt][1], L, R);
  }

  void update(int l, int r, int &rt, int p) {
    if (!rt) rt = ++tot;
    if (l == r) {
      tr[rt].min = tr[rt].max = p;
      tr[rt].sum1 = tr[rt].sum2 = 0;
      return;
    }
    int mid = (l + r) >> 1;
    if (p <= mid)
      update(l, mid, ch[rt][0], p);
    else
      update(mid + 1, r, ch[rt][1], p);
    if (ch[rt][0] && ch[rt][1])
      tr[rt] = merge(tr[ch[rt][0]], tr[ch[rt][1]]);
    else if (ch[rt][0])
      tr[rt] = tr[ch[rt][0]];
    else
      tr[rt] = tr[ch[rt][1]];
  }

  int merge(int x, int y) {
    if (!x || !y) return x + y;
    int rt = ++tot;
    ch[rt][0] = merge(ch[x][0], ch[y][0]);
    ch[rt][1] = merge(ch[x][1], ch[y][1]);
    if (ch[rt][0] && ch[rt][1])
      tr[rt] = merge(tr[ch[rt][0]], tr[ch[rt][1]]);
    else if (ch[rt][0])
      tr[rt] = tr[ch[rt][0]];
    else
      tr[rt] = tr[ch[rt][1]];
    return rt;
  }
} seg;

int root[MAXN], samcnt = 1;
int ch[MAXN][CHARSET], link[MAXN];
int len[MAXN], pos[MAXN], st[MAXN][ST], dep[MAXN];

inline void extend(int c, int id) {
  static int lst = 1;
  int cur = ++samcnt, p = lst;
  lst = pos[id] = cur, len[cur] = len[p] + 1;
  while (p && !ch[p][c]) ch[p][c] = cur, p = link[p];
  if (!p)
    link[cur] = 1;
  else {
    int q = ch[p][c];
    if (len[p] + 1 == len[q])
      link[cur] = q;
    else {
      int nq = ++samcnt;
      len[nq] = len[p] + 1;
      memcpy(ch[nq], ch[q], sizeof(ch[q]));
      link[nq] = link[q], link[q] = link[cur] = nq;
      while (p && ch[p][c] == q) ch[p][c] = nq, p = link[p];
    }
  }
}

int n;
int heads[MAXN], ecnt;

struct Edge {
  int v, nxt;
} e[MAXN << 1];

inline void add(int u, int v) { e[++ecnt] = (Edge){v, heads[u]}, heads[u] = ecnt; }

void dfs(int u) {
  st[u][0] = link[u];
  for (int i = 1; i < ST; ++i) st[u][i] = st[st[u][i - 1]][i - 1];
  for (int i = heads[u]; i; i = e[i].nxt) {
    int v = e[i].v;
    dep[v] = dep[u] + 1;
    dfs(v);
    if (u != 1) root[u] = seg.merge(root[u], root[v]);
  }
}

inline void prework() {
  for (int i = 2; i <= samcnt; ++i) add(link[i], i);
  for (int i = 1; i <= n; ++i) seg.update(1, n, root[pos[i]], i);
  dfs(1);
}

inline LL C(int n) {
  if (n < 2) return 0;
  return n * 1LL * (n - 1) / 2;
}

inline LL query(int l, int r) {
  int slen = r - l + 1, u = pos[r];
  for (int i = ST - 1; i >= 0; --i)
    if (len[st[u][i]] >= slen) u = st[u][i];
  int L = tr[root[u]].min, R = tr[root[u]].max;
  if (L < R - slen * 2 + 1 && seg.queryMax(1, n, root[u], L, R - slen) - slen + 1 > L)
    return C(n - 1);
  if (R - slen + 1 <= L) {
    Node cur = tr[root[u]];
    int lm = R - slen + 1;
    LL ans = cur.sum1 - cur.sum2 * lm + C(L - lm) + (L - lm) * 1LL * (n - slen);
    return C(n - 1) - ans;
  } else {
    seg.tmp = (Node){0, 0, 0, 0};
    int lm = R - slen + 1, poslm = seg.queryMax(1, n, root[u], 1, lm);
    seg.query(1, n, root[u], poslm, L + slen - 1);
    Node cur = seg.tmp;
    int p1 = seg.queryMax(1, n, root[u], 1, L + slen - 1);
    int p2 = seg.queryMin(1, n, root[u], L + slen, n);
    LL ans = cur.sum1 - cur.sum2 * lm + (p2 > lm ? (L - (p1 - slen + 1)) * 1LL * (p2 - lm) : 0);
    return C(n - 1) - ans;
  }
}

int q;
char str[MAXN];

inline int main() {
  cin >> n >> q >> (str + 1);
  for (int i = 1; i <= n; ++i) extend(str[i] - '0', i);
  prework();
  for (int l, r; q; --q) {
    cin >> l >> r;
    cout << query(l, r) << '\n';
  }
  return 0;
}

}  // namespace BlueQuantum

int main() {
#ifndef ONLINE_JUDGE
#ifdef LOCAL
  freopen("/tmp/CodeTmp/testdata.in", "r", stdin);
  freopen("/tmp/CodeTmp/testdata.out", "w", stdout);
#else
  freopen("P4384 [八省联考2018] 制胡窜.in", "r", stdin);
  freopen("P4384 [八省联考2018] 制胡窜.out", "w", stdout);
#endif
#endif

  ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
  return BlueQuantum::main();
}
